{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "希尔排序\n",
    "\n",
    "\n",
    "希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。\n",
    "\n",
    "    该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 举例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例\n",
    "\n",
    "第一次 gap = 10/2 = 5\n",
    "\n",
    "49 38 65 97 26 13 27 49 55 4\n",
    "\n",
    "1A 1B\n",
    "2A 2B\n",
    "3A 3B\n",
    "4A 4B\n",
    "5A 5B\n",
    "\n",
    "1A, 1B, 2A, 2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素， 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。\n",
    "变成：\n",
    "\n",
    "    13 27 49 55 4 49 38 65 97 26  （依次取每个组内的第1个值，第二个值）\n",
    "\n",
    "第二次 gap = 5 / 2 = 2\n",
    "1A 1B 1C 1D 1E\n",
    "2A 2B 2C 2D 2E\n",
    "\n",
    "（13,49,4,38,97） 和（27,55,49,65,26）\n",
    "排序后：在依次选择：\n",
    "\n",
    "    4 26 13 27 38 49 49 55 97 65\n",
    "\n",
    "第三次 gap = 2 / 2 = 1\n",
    "1A 1B 1C 1D 1E 1F 1G 1H 1I 1J\n",
    "\n",
    "第四次 gap = 1 / 2 = 0 排序完成得到数组：\n",
    "\n",
    "    4 13 26 27 38 49 49 55 65 97\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shell_sort(nums):\n",
    "    n = len(nums)\n",
    "    print(n,nums)\n",
    "    gap = n // 2\n",
    "    \n",
    "    while gap >= 1:\n",
    "        for i in range(gap, n):\n",
    "            tmp = nums[i]\n",
    "            j = i\n",
    "            # 妙哉，把（13,49,4,38,97）和（27,55,49,65,26）的序列交叉进行插入排序。  精髓。\n",
    "            while j - gap >= 0 and nums[j - gap] > tmp:   \n",
    "                nums[j] = nums[j - gap]\n",
    "                j -= gap\n",
    "            nums[j] = tmp\n",
    "        print(gap,nums)\n",
    "        gap = gap // 2\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 [49, 38, 65, 97, 26, 13, 27, 49, 55, 4]\n",
      "5 [13, 27, 49, 55, 4, 49, 38, 65, 97, 26]\n",
      "2 [4, 26, 13, 27, 38, 49, 49, 55, 97, 65]\n",
      "1 [4, 13, 26, 27, 38, 49, 49, 55, 65, 97]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[4, 13, 26, 27, 38, 49, 49, 55, 65, 97]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [49, 38, 65, 97, 26, 13, 27, 49, 55, 4]\n",
    "shell_sort(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
